/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //平衡括号字符串的最少插入次数
    public int minInsertions(String s) {
        char[] chars = s.toCharArray();
        int res = 0, N = chars.length, left = 0;
        for (int i = 0; i < N; i++) {
            if (chars[i] == '(') {
                left++;
            } else {
                // 没有左括号了，需要加一个左括号，res++
                if (left == 0) res++;
                else left--;

                // 以下两种情况只有一个右括号，需要再加一个右括号，res++
                if (i == N - 1 || chars[i + 1] != ')') res++;
                else i++;
            }
        }
        return res + left * 2; // 剩余的左括号需要2倍的右括号匹配
    }
}
